package com.lsa.letcode.the94.btInorderTraversal;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

import com.lsa.letcode.common.TreeNode;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
    	List<Integer> visited = new ArrayList<Integer>();
    	class StackFrame{
    		int step; // 0 - left, 1 - visit, 2 - right, 3 - return
    		TreeNode root;
			StackFrame(TreeNode root) {
				this.root = root;
			}
    	}
    	
    	Deque<StackFrame> stack = new ArrayDeque<StackFrame>();
    	stack.add(new StackFrame(root));
    	while(!stack.isEmpty()) {
    		StackFrame f = stack.peek();
    		if (f.root == null){
    			stack.pop();
    		}
    		else {
    			int step = f.step++;
    			switch (step) {
    			case 0:
    				stack.push(new StackFrame(f.root.left));
    				break;
    			case 1:
    				visited.add(f.root.val);
    				break;
    			case 2:
    				stack.push(new StackFrame(f.root.right));
    				break;
    			case 3:
    				stack.pop();
    				break;
    			}
    		}
    	}
    	
        return visited;
    }
    
    public List<Integer> inorderTraversalRec(TreeNode root) {
    	List<Integer> visited = new ArrayList<Integer>();
    	doInorderTraversalRec(root, visited);
        return visited;
    }
    
    private void doInorderTraversalRec(TreeNode root, List<Integer> visited) {
    	if (root == null){
    		return;
    	}
    	
    	doInorderTraversalRec(root.left, visited);
    	visited.add(root.val);
    	doInorderTraversalRec(root.right, visited);
    }
}